nOvde je problem proceniti dužinu najkraćeg puta između dve
adrese u mreži (nadalje, to će se odnositi na “tačnu razdaljinu”). Dva
alternativna pristupa će biti razmatrana ovde:
a)Proračunavanje tačne razdaljine
između svih parova adresa u mreži, i njihovo skladištenje u tabeli
rastojanja za naredno korišćenje.
b)Proračunavanje tačne razdaljine
između dve adrese svaki put kada je to potrebno.
n Prvi pristup nije realan
za velike mreže, iz razloga što bi tada tabela rastojanja bila prevelika da bi bila
postavljena u glavnu memoriju ( primetimo da N adresa generišu O(N2) parovnih rastojanja). Sa druge strane izračunavanje tačne razdaljine “po zahtevu” je
nefunkcionalno zbog mnogo vremena potrošenog na računanje. Procena
najkraće putanje je skupa jer dve tačke mogu biti dosta udaljene, i
specifične potrebe moraju biti uračunate pri proceni, kao što su jednosmerne ulice i
zastoji pri skretanju u levo.
n Kako bi dosledno
omogućili kraće vreme izračunavanja, uzeli smo međupristup
tako
što smo podelili mrežu ulica na 502 zone veličine kvadratnog kilometra. Unutar svake zone,
najvažnija raskrsnica je definisana kao “centar” zone. Tačne razdaljine su
izračunate između svakog para centara, i postavljene su u tabelu rastojanja. Veličina
tabele je oko 1MB, i može biti postavljena u glavnu memoriju